// https://leetcode.cn/problems/sliding-window-maximum/

package leet239slidewindowmax

// 对于 nums=[1,3,-1,-3,5,3,6,7]，k=3 ，寻找窗口大小为k的滑动窗口的所有的最大值
// 暴力解法，每一次移动滑动窗口，都对窗口内的元素进行排序。
// 暴力解法最大的问题是，之前已经进行过排序的元素也要因为窗口的移动而重新排序。暴殄天物。
// 为了解决暴力解法的问题，我们可以根据一个特点来进行优化：
// 这个特点就是每一个新加入的元素都无需和之前的所有元素都进行无差别的比较，只比较那些需要比较的元素就行，
// 那么哪些元素是需要比较的呢？或者说哪些元素不需要比较我们可以直接丢弃呢？
// 答案：如果我们新加入的元素比窗口中已经存在（假如窗口中存在 x/y/z）的某些元素(假如为x/y)大的话，那么x/y就不需要比较了，可以直接丢弃掉了，
//       因为x/y不可能是窗口中的最大值了，x/y稍后肯定也比当前值先一步被窗口划过了。
//       所以这么一来的话，窗口中存在的元素肯定是比新加入元素要大的元素，而且前一个元素如果前边还有元素，那么后者比前者还要打，也就是说这是一个单调递减的队列。
//       也就是说我们可以使用一个单调递减的队列来存储窗口中的元素。
// 这个单调队列要想维护好，在当前的上下文中必须有如下的操作：
// 队列中存储着元素的索引，因为窗口的移动会导致元素从队列中移除，我们要判断移除的是不是队列的头元素。
// 队列的头元素就是窗口中的最大值。他的尾向元素都是比他索引靠后且比他小的元素。
// 这样每一次窗口的移动，我们先根据滑出的索引来判断队列的头元素是否需要移除，如果需要移除，则将队列的头元素出队。
// 然后再将新加入的元素的索引入队，同时维护队列的单调性。
// 这样每一次窗口移动完毕后，队列的头元素就是窗口中的最大值。
// 这样我们就可以在O(n)的时间复杂度内获取窗口中的最大值了。

// 具体过程：如下队列，队列头在左侧，队尾在右侧
// 第一次入队列 1 ， 没啥好比较的，队列成员就是： {1}
// 第二次入队列 3 ，3之前的元素1比3要小，所以在当前窗口中它已经没有存在感了，剔除掉，队列成员就是： {3}
// 第三次入队列 -1 ，-1比3小，所以直接入队，队列成员就是： {3 -1}。 最大值为头元素3.
// 第四次入队列 -3 ，从此开始理论上索引0处的元素应该出队列，但是现在头元素索引是1，说明那个元素已经不存在了，-3比先入队列的-1要小，更别说前边的3了，所以直接入队，队列成员就是： {3 -1 -3}。最大值为头元素3.
// 第五次入队列 5 ，索引1处主动出队列，头元素恰好是索引1处的元素，所以队里成员首先变为{-1，-3}，5比-1大，所以-1和-3都要出队列，队列成员就是： {5}。最大值为头元素5
// 第六次入队列 3 ，索引2处主动出队列，但是不存在该元素，忽略。然后3比5小，所以直接入队列，队列成员就是： {5 3}。最大值为头元素5
// 第七次入队列 6 ，索引3处主动出队列，但是不存在该元素，忽略。然后6比5大，所以5和3都要出队列，队列成员就是： {6}。最大值为头元素6
// 第八次入队列 7 ，索引4处主动出队列，但是不存在该元素，忽略。然后7比6大，所以6和3都要出队列，队列成员就是： {7}。最大值为头元素7
// 这样我们就可以在O(n)的时间复杂度内获取窗口中的最大值了。

func MaxSlidingWindow(nums []int, k int) []int {
	if len(nums) == 0 || k == 0 {
		return nil
	}
	if k == 1 {
		return nums
	}
	// 定义一个单调递减的队列，存储元素的索引
	queue := make([]int, 0)
	res := make([]int, 0)
	for i := 0; i < len(nums); i++ {
		// 如果队列不为空，并且队列的头元素已经不在窗口中了，则出队 - 主动出队。
		if len(queue) > 0 && queue[0] <= i-k {
			queue = queue[1:]
		}
		// 如果队列不为空，并且队列的尾元素比当前元素小，则出队 - 被动出队。
		// 这里的被动出队是指当前元素比队列的尾元素大，所以队列的尾元素已经没有存在感了。
		for len(queue) > 0 && nums[queue[len(queue)-1]] < nums[i] {
			queue = queue[:len(queue)-1]
		}
		// 当前元素的索引肯定是要入队列的，他能产生的影响在于是否能够通过对对碰的模式将前边比自己小的元素剔除掉，也就是让他们出队。
		queue = append(queue, i)
		// 已经开始移动窗口了，窗口的大小为k，所以当i大于等于k-1时，才开始记录结果。
		if i >= k-1 {
			res = append(res, nums[queue[0]])
		}
	}
	return res
}
